package crazy;

public class BinaryInsertSort
{

	public static void main(String[] args)
	{
		DataWrap[] data = { new DataWrap(21, ""), new DataWrap(30, ""),
				new DataWrap(49, ""), new DataWrap(30, "*"),
				new DataWrap(16, ""), new DataWrap(9, "") };
		
		System.out.println("before sorting-->"+java.util.Arrays.toString(data));
		binaryInsertSort(data);
		System.out.println("after sorting-->"+java.util.Arrays.toString(data));
	}
	
	public static void binaryInsertSort(DataWrap[] data)
	{
		int arrayLength = data.length;
		
		for (int i = 1; i < arrayLength; i++)
		{
			DataWrap tmp = data[i];
			int low = 0;
			int high = i-1;
			
			while (low<=high)//找到的low位置就是要插入值的位置
			{
				int mid = (low+high)/2;
				if (tmp.compareTo(data[mid])>0)
				{
					low = mid + 1;
				}
				else 
				{
					high = mid -1;
				}
			}
			for (int j = i; j > low; j--)//和for(int i=0;i<length;i++) 刚好是想法的操作
			{
				data[j] = data[j-1];
			}
			data[low] = tmp;//把值插入进去
			System.out.println(java.util.Arrays.toString(data));
		}
	}

}
